1. Technical Field
The present invention relates generally to the execution of computer programs on computing machines. More specifically, the present invention relates to a system for the execution of computer programs on computing machines that utilize a two-tier memory hierarchy comprised of a small, fast “local” memory for program execution and a larger, slower “bulk” memory for program storage.
2. Background Information
Hierarchical memory systems are a well-known solution to the problem of connecting increasingly fast Central Processing Units (CPUs) with increasingly large, slow bulk storage. One or more additional stages of memory, decreasing in size and increasing in speed as one approaches the CPU, are inserted between the CPU and bulk storage. Often, the intermediate memories are too small to contain the entire application at one time. Therefore, paging is used to transfer code and data blocks between adjacent memories in response to the flow of the executing program. The problem within this context is designing and implementing a paging mechanism that effectively incorporates several main design considerations including:                Partitioning the program into blocks        Uniquely identifying each block        Trigger mechanism whereby program execution results in block paging requests        Fast memory management policy for block placement and replacement        
Previous solutions to this paging problem generally fall into two categories: hardware caching (including the well-known virtual memory) and manual paging. Hardware caching is a well-known automatic mechanism that employs special-purpose hardware to monitor real-time memory access activity, detect cache misses, transfer fixed-size memory blocks (lines) between bulk memory and fast memory, and manage the placement and replacement of these lines within fast memory. The cache hardware design effectively partitions applications into fixed-size pieces, based on the application's location in bulk memory, without regard for the application's structure. The placement/replacement policy is typically fixed (e.g. Least Recently Used, N-way Set Associative, Random Replacement algorithms) and designed to offer acceptable performance over a class of applications rather than being tuned for a specific application. Adoption of a Hardware Caching solution negatively impacts hardware complexity and power dissipation and, for architectures with multiple, concurrently-accessible memories (such as the Harvard architecture, common to most digital signal processors), requires cache hardware for each memory subsystem.
In manual paging, a programmer manually examines an application's source code and design documentation to understand the various functions embedded within the application and to decipher the application's program structure. Then, with knowledge of the target platform's fast memory resources and architecture, the programmer manually partitions the application and builds in a custom paging mechanism. This paging mechanism is actively managed during run time by program instructions added to the application by the programmer to page the resulting partitions into and out of fast memory as needed in real-time or near real-time. Manual paging requires no special-purpose hardware, but relies heavily on the capabilities of the programmer. The need to understand the underlying application involves substantial effort, especially if the programmer incorporating the paging mechanism is not the application's original programmer. Introduction of a platform with further-reduced fast memory requires another manual paging effort, perhaps by a different programmer. As application complexity increases and fast memory sizes decrease, the ability to manually implement the paging process is negatively impacted by the number of partitions involved and by errors introduced by the programmer.